An activity which is fundamental to the operation of a packet-switched communication system is a search in a database for an entry corresponding to an input key. This is required for many purposes. One is to obtain forwarding data for a packet so that the packet can be forwarded from the appropriate port or ports of a switch or router. Such forwarding data may constitute all or part of the data ‘associated’ with an entry corresponding to the input key; the input key may be a network destination address extracted from an addressed packet.
Different kinds of search engine exist for the performance of searches of this nature. One kind comprises a content addressable memory (CAM) which can test an input key simultaneously against a multiplicity of stored words. A principal disadvantage of CAMs is their high power consumption, which tends to restrict the number of addresses that can in practice be stored. Another is a hashing engine which reduces a search word to a much shorter word, which indexes a database. Since different search keys can be hashed to the same (shorter) word, it is necessary to test each entry for a full match with the search word and to provide links between entries corresponding to the same hash. A third, and quite versatile, kind is a multi-way tree search engine, called usually a trie search engine, which at each intermediate stage of a search provides a pointer specifying the address of a block of entries (sometimes called ‘node’) but does not distinguish between those entries. Such a block is accessed at the next stage of the search and the segment of the key which is employed in that stage obtains a particular entry within the block and so on until the search reaches an entry which indicates completion of the search. Completion may be signified by access to ‘associated data’ (such as forwarding data) or by termination of the search as unsuccessful. Although trie search engines have no inherent limitation on their size and can provide different search strategies, their disadvantage is the number of cycles or stages they need to complete a search.
Typically a trie search employs either four or seven bits at each stage. Whether the search strategy employs four bits or seven bits at each stage depends on whether one desires a faster search or a slower more versatile search.
If, for example a trie search is performed for a host address conforming to Internet Protocol version 4 (IPv4) and having therefore 32 bits, a full trie search requires at most five stages if seven bits are used at each stage.
However, a trie search engine which is required to perform a corresponding search for a host address conforming to Internet Protocol version 6 (IPv6), having therefore 128 bits, would require 19 cycles to complete using key segments of seven bits and 32 cycles to complete using key segments of four bits. Such a number of cycles would make a trie search undesirable for long search keys such as destination addresses conforming to IPv6.